package com.explorati.tanxin.LeetCode455.assigncookies;

import java.util.Arrays;
import java.util.Collections;

/**
 * 455. Assign Cookies 贪心算法
 * 
 * 分饼干问题 你要分饼干给你的孩子 一个孩子只能给一块饼干，每个饼干有一个值，每个孩子有一个满足值，满足值即每块饼干的值 看怎么分能够满足最多的孩子
 * 
 * @author explorati
 *
 */
public class Solution {
	// g[i]是孩子满足值，s是饼干值
	public int findContentChildren(int[] g, int[] s) {
		// 贪心算法必须先对两个数组排序
		Arrays.sort(g);
		Arrays.sort(s);

		int res = 0;
		int i = s.length - 1, j = g.length - 1;
		while (i >= 0 && j >= 0) {
			if (s[i] >= g[j]) {
				res++;
				i--;
				j--;
			} else {
				j--;
			}
		}
		return res;
	}
}
